package cn.suchan.jianzhi.q22_tree;

import java.util.ArrayList;

/**
 * 知识点：从上往下打印二叉树
 * 题目描述
 * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 *
 * @author suchan
 * @date 2019/05/27
 */
public class Solution {

    /**
     * 使用两个队列一个存放节点，一个存放值。
     * 先将根节点加入到treeList集合中，然后遍历treeList集合中的元素，
     * 遍历过程中，访问该元素的左右节点，再将左右子节点加入到result集合中。
     *
     * @param root
     * @return
     */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        // 辅助集合
        ArrayList<TreeNode> treeList = new ArrayList<>();

        if (root == null) {
            return result;
        }
        treeList.add(root);
        for (int i = 0; i < treeList.size(); i++) {
            if (treeList.get(i).left != null) {
                treeList.add(treeList.get(i).left);
            }
            if (treeList.get(i).right != null) {
                treeList.add(treeList.get(i).right);
            }
            result.add(treeList.get(i).val);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        node5.left = node10;

        Solution solution = new Solution();
        ArrayList<Integer> result = solution.PrintFromTopToBottom(node1);

        result.forEach(node -> System.out.println(node));
    }
}
